package com.example.zhucongjdbc;

import java.util.*;

/**
 * @Description:
 * @Author:mayc
 * @Date:2020/3/6 18:25
 */
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String firstLine = input.nextLine();
        String[] fl = firstLine.split("\\s+");
        Integer totalMoney = Integer.valueOf(fl[0]);
        Integer length = Integer.valueOf(fl[1]);
        Map<Integer, Item> map = new HashMap<>();
        int i = 1;
        while (true) {
            String item = input.nextLine();
            String[] item_ = item.split("\\s+");
            Integer v = Integer.valueOf(item_[0]);
            Integer p = Integer.valueOf(item_[1]);
            Integer q = Integer.valueOf(item_[2]);
            if (q == 0) { // 主件
                Item it = new Item();
                it.setPrice(v);
                it.setWeigth(p);
                map.put(i, it);

            } else { // 如果是附件，则先获取该附件的主件
                Item item1 = map.get(q);
                if (item1 != null) {
                    List<Item> fls = item1.getFj();
                    if (fls == null) {
                        fls = new ArrayList<>();
                    }
                    Item fj = new Item();
                    fj.setPrice(v);
                    fj.setWeigth(p);
                    item1.setFj(fls);
                }
                map.put(q, item1);
            }
            i++;
            length--;
            if (length == 0) break;
        }
        // 开始检测
        int smoney = 0;
        List<Integer> maxPV = new ArrayList<>();
        for (Map.Entry<Integer, Item> entry : map.entrySet()) {
            Item master = entry.getValue();
            List<Item> slaves = master.getFj();
            int lsMaxPV = 0;
            if (master.getPrice() < totalMoney) {
                lsMaxPV = master.getPrice() * master.getWeigth();
                smoney = totalMoney - master.price;
            }
            if (smoney > 0 && slaves != null && slaves.size() > 0) {
                if (slaves.size() == 1) {
                    Item slave = slaves.get(0);
                    if (slave != null) {
                        lsMaxPV += (slave.getPrice() * slave.getWeigth());
                        smoney -= slave.price;
                    }
                }
            }

        }

    }

    static class Item {
        private Integer price;
        private Integer weigth;
        private List<Item> fj;

        public Integer getPrice() {
             return this.price;
        }

        public void setPrice(Integer price) {
            this.price = price;
        }

        public Integer getWeigth() {
            return weigth;
        }

        public void setWeigth(Integer weigth) {
            this.weigth = weigth;
        }

        public List<Item> getFj() {
            return fj;
        }

        public void setFj(List<Item> fj) {
            this.fj = fj;
        }
    }
}
